package 力扣日常刷题.木22一月.第13天0121;

/**
 * @author 帅小伙
 * @date 2022/1/21
 * @description
 */
public class Demo42动态规划统计全1子矩阵 {


    public static void main(String[] args) {
        Demo42动态规划统计全1子矩阵 test = new Demo42动态规划统计全1子矩阵();
        int[][] arr = new int[][]{{1,0,0,0,0},{1,1,1,1,1}};
        test.numSubmat(arr);
    }

    public int numSubmat(int[][] mat) {
        int ans = 0;
        int n = mat.length,m = mat[0].length;
        int[][]dp = new int[n][m];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (mat[i][j] == 1) {
                    // 宽度
                    dp[i][j] = j == 0 ? 1: dp[i][j-1]+1;
                    // i j 是右下角  枚举矩阵的高度
                    int min = Integer.MAX_VALUE;
                    for (int h = 0; h <= i ; h++) {
                        if(mat[i-h][j] == 0)
                            break;
                        min = Math.min(min,dp[i-h][j]);
                        ans += min;
                    }
                }
            }
        }
        return ans;

    }
}
